1. Field of the Invention
The present invention relates to a system for improving the computational efficiency of protocols wherein modular inverses are to be computed by a slow apparatus connected by a communication link to a faster but potentially hostile device.
The invention can be used advantageously in order to speed-up the Digital Signature Algorithm (DSA), proposed by the US National Institute of Standards and Technology (A Proposed Federal Information Processing Standard for Digital Signature Standard (DSS), Federal Register Announcement, Aug. 30, 1991, p 42980-42982).
2. Discussion of the Related Art
Although file idea of inserting a chip into a plastic card is relatively old (The first patents are now seventeen years old), practical applications only emerged a few years ago because of some computational limitations of the cards. Progress in storage capacity, security and circuit technology (for example EEPROM) leads quickly to new generations of cards and more ambitious applications such as the new emerging US Digital Signature Standard.
The Digital Signature Algorithm (DSA, US patent application No. 07/738,431 entitled "Digital Signature Algorithm") was proposed by the US National Institute of Standards and Technology to provide an appropriate core for applications requiring a digital rather than written signature. The DSA digital signature is a pair of large numbers represented in a computer as strings of binary digits. The digital signature is computed using a set of rules (i.e. the DSA) and a set of parameters such that the identity of the signatory and integrity of the data can be verified. The DSA provides the capability to generate and verify signatures.
Signature generation makes use of a private key to generate a digital signature, Signature verification makes use of a public key which corresponds to, but is not the same as, the private key. Each user possesses a private and a public key pair. Public keys are assumed to be known to the public in general whereas private keys are never shared, Anyone can verify the signature of a user by employing that user's public key. Signature generation can be performed only by the user's private key.
DSA parameters are:
1 A prime modulus p where 2.sup.L-1 &lt;p&lt;2.sup.L for 512.ltoreq.L.ltoreq.1024 and L=64 .alpha. for some .alpha.. PA0 2 A prime q such that 2.sup.159 &lt;q&lt;2.sup.160 and p-1 is a multiple of q. PA0 3 A number g, of order q modulo p such that ##EQU1## where h is any interger such that 1&lt;h&lt;p-1 and ##EQU2## 4 A number x, generate randomly or pseudo randomly. PA0 1 w=1/S mod q PA0 2 u.sub.1 =m w mod q PA0 3 u.sub.2 =r w mod q PA0 4 v=(g.sup.u 1 y.sup.u 2 mod p) mod q PA0 5 And checks if v and r match to accept or reject the signature.
5 A number y defined by the relation: y=g.sup.x mod p.
6 A number k generated randomly or pseudo-randomly such that 0&lt;k&lt;q.
The integers p, q and g are system parameters and can be public and/or common to a group of users. The signer's private and public keys are respectively x and y. Parameters x and k are used for signature generation only and must be kept secret. Parameter k must be regenerated for each signature.
In order to sign a message m (hashed value of a primitive file M), the signer computes the signature {r, s} by: ##EQU3## Wherein division by k is done modulo q (that is, l/k is the number k' such that k k'=1 mod q).
For instance, if q=5 and k=3 then 1/k=2 since 3.times.2=6=1 mod 5.
After checking that r.noteq.0.noteq.s, as explained the DSA description, the signature {r, s} is sent to the verifier who computes: